Several algorithms to predict the next place visited by a user have been 
proposed in the literature. The accuracy of these algorithms – measured as 
the ratio of the number of correct predictions and the number of all computed 
predictions – is typically very high. In this paper, we show that this good 
performance is due to the high predictability intrinsic in human mobility. We 
also show that most algorithms fail to correctly predict transitions, i.e. 
situations in which users move between different places. To this end, we 
analyze the performance of 18 prediction algorithms focusing on their ability 
to predict transitions. We run our analysis on a data set of mobility traces 
of 37 users collected over a period of 1.5 years. Our results show that even 
algorithms achieving an overall high accuracy are unable to reliably predict 
the next location of the user if this is different from the current one. 
Building upon our analysis we then present a novel next-place prediction 
algorithm that can both achieve high overall accuracy and reliably predict 
transitions. Our approach combines all the 18 algorithms considered in our 
analysis and achieves its good performance at the cost of a higher 
computational and memory overhead.